package com.chenyi.data.structure.hash;

import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

/**
 * @author chenyi
 * @className HashTable
 * @date 2022/4/18 19:14
 */
public class HashTable<E> {

    public static void main(String[] args) {
        HashTable<Test> hashTable = new HashTable<>(20);
        List<String> list = new ArrayList<>(1000);
        for (int i = 0; i <= 100; i++) {
            list.add(hashTable.putVal(new Test(i + "" + Math.random(), i)));
        }
        String s = list.get(100);
        System.out.println("key=" + s);

        Test test = hashTable.get(s);
        System.out.println(test);

        System.out.println(hashTable.remove(s));
        System.out.println(hashTable.get(s));
    }

    static class Node<E> {
        String key;
        Node<E> head;
        int hash;
        E value;
        Node<E> next;

        public Node(String key, int hash, E value, Node<E> next) {
            this.key = key;
            this.hash = hash;
            this.value = value;
            this.next = next;
        }

        public Node() {
        }

        private Node<E> get(String key) {
            if (head == null) {
                return null;
            }
            Node<E> curNode = head;
            while (!curNode.key.equals(key)) {
                curNode = curNode.next;
                if (curNode == null) {
                    return null;
                }
            }
            return curNode;
        }

        private Node<E> getPrevNode(String key) {
            if (head == null) {
                return null;
            }
            Node<E> curNode = head;
            Node<E> prevNode = curNode;
            while (!curNode.key.equals(key)) {
                prevNode = curNode;
                curNode = curNode.next;
                if (curNode == null) {
                    return null;
                }
            }
            return prevNode;
        }

        @Override
        public String toString() {
            return "Node=" + value;
        }
    }

    private Node<E>[] table;

    private int size;

    private static final int DEFAULT_SIZE = 16;

    @SuppressWarnings("unchecked")
    public HashTable(int size) {
        this.size = size;
        table = (Node<E>[]) new Node[size];
        for (int i = 0; i < table.length; i++) {
            table[i] = (Node<E>) new Node();
        }
    }

    @SuppressWarnings("unchecked")
    public HashTable() {
        this.size = DEFAULT_SIZE;
        table = (Node<E>[]) new Node[size];
        for (int i = 0; i < table.length; i++) {
            table[i] = (Node<E>) new Node();
        }
    }

    public String putVal(E e) {
        // 获取hash值
        int hash = hash(e);
        // 从当前hash获取节点
        Node<E> curNode = table[hash];
        String key = UUID.randomUUID().toString();
        if (curNode.head == null) {
            curNode = new Node<>(key, hash, e, null);
            curNode.head = curNode;
            table[hash] = curNode;
            return key;
        }
        Node<E> head = curNode;
        while (curNode.next != null) {
            curNode = curNode.next;
        }
        curNode.next = new Node<>(key, hash, e, null);
        curNode.next.head = head;
        return key;
    }

    private Node<E> getNode(String key) {
        judgeKey(key);
        for (int i = 0; i < size; i++) {
            Node<E> tableNode = table[i];
            Node<E> eNode = tableNode.get(key);
            if (eNode != null) {
                return eNode;
            }
        }
        return null;
    }

    private Node<E> getPrevNode(String key) {
        judgeKey(key);
        for (int i = 0; i < size; i++) {
            Node<E> tableNode = table[i];
            Node<E> eNode = tableNode.getPrevNode(key);
            if (eNode != null) {
                return eNode;
            }
        }
        return null;
    }

    public E get(String key) {
        Node<E> node = getNode(key);
        if (node != null) {
            return node.value;
        }
        return null;
    }

    public boolean remove(String key) {
        Node<E> node = getNode(key);
        Node<E> prevNode = getPrevNode(key);
        if (node != null && prevNode != null) {
            if (node.next == null && node != prevNode) {
                prevNode.next = null;
            } else if (node == prevNode){
                table[node.hash] = node.next;
                table[node.hash].head = node.next;
                node = null;
            } else {
                prevNode.next = node.next;
                node = null;
            }
            return true;
        }
        return false;
    }

    private int hash(Object value) {
        int h;
        if (value == null) {
            return 0;
        }
        h = (h = value.hashCode()) ^ (h >>> 16);
        if (h >= size) {
            h = h % size;
        } else if (h < 0) {
            h = Math.abs(h);
            h = h % size;
        }
        return h;
    }

    private void judgeKey(String key) {
        if (key == null) {
            throw new RuntimeException("key is null");
        }
    }


}
